package com.ztom.top100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 最大矩形
 * <p>
 * https://leetcode-cn.com/problems/maximal-rectangle/
 *
 * @author ZhangTao
 */
public class Code36MaximalRectangle {

    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        // 用一个数组将矩形转化为柱状图:
        // 以每一行作为底, 列上连续的 1 作为高度
        int[][] heights = new int[m][n];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    heights[i][j] = (i == 0) ? 1 : heights[i - 1][j] + 1;
                }
            }
        }
        int max = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int[] height : heights) {
            for (int i = 0; i < height.length; i++) {
                while (!stack.isEmpty() && height[stack.peekLast()] >= height[i]) {
                    Integer top = stack.pollLast();
                    int lMin = stack.isEmpty() ? -1 : stack.peekLast();
                    max = Math.max(max, (i - lMin - 1) * height[top]);
                }
                stack.addLast(i);
            }
            while (!stack.isEmpty()) {
                Integer top = stack.pollLast();
                int lMin = stack.isEmpty() ? -1 : stack.peekLast();
                int rMin = height.length;
                max = Math.max(max, (rMin - lMin - 1) * height[top]);
            }
        }

        return max;
    }
}
